"""P9 9. 暴力递归"""


"""
前缀树可以快速查询某个字符串是否存在和包含某个前缀的字符串数量
"""


class TrieNode:
    """前缀树的节点"""

    def __init__(self):
        self.through = 0
        self.end = 0
        self.next_nodes = dict()


class Trie:
    """前缀树"""

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        """插入一个字符串"""
        if not word:
            return
        node = self.root
        node.through += 1
        for char in word:
            if char not in node.next_nodes:
                node.next_nodes[char] = TrieNode()
            node = node.next_nodes[char]
            node.through += 1
        node.end += 1

    def search(self, word: str) -> int:
        """搜索word的数量"""
        if not word:
            return 0
        node = self.root
        for char in word:
            if char not in node.next_nodes:
                return 0
            node = node.next_nodes[char]
        return node.end

    def prefix_number(self, pre: str):
        """获得包含前缀pre的字符串数量"""
        if not pre:
            return 0
        node = self.root
        for char in pre:
            if char not in node.next_nodes:
                return 0
            node = node.next_nodes[char]
        return node.through

    def delete(self, word: str):
        """在前缀树中删除word字符串"""
        if self.search(word) == 0:
            return
        node = self.root
        for char in word:
            node.through -= 1
            if node.through == 0:
                node.next_nodes.pop(char)
                return
            node = node.next_nodes[char]
        node.end -= 1


"""
贪心算法：
在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，
最终得到一个答案的算法，叫做贪心算法
也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解
局部最优  -?->  整体最优

安排会议：选择最早结束的会议

贪心算法在笔试的解题套路：
1、实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
2、脑补出贪心策略A、贪心策略B、贪心策略C……
3、用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
4、不要去纠结贪心策略的证明

贪心策略在实现时，经常使用到的技巧：
1、根据某标准建立一个比较器来排序
2、根据某标准建立一个比较器来组成堆
"""


def is_valid(record: list, i: int, j: int):
    """判断i，j位置是否合法"""
    for k in range(i):
        if j == record[k] or abs(record[k] - j) == abs(i - k):
            return False
    return True


def n_q(i: int, record: list, n: int):
    """N皇后问题，时间复杂度：N ** N"""
    # record = [-1] * n
    if i == n:
        return 1
    result = 0
    for j in range(n):
        if is_valid(record, i, j):
            record[i] = j
            result += n_q(i + 1, record, n)
    return result
